/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class RepeatedStringMatch {
	public int repeatedStringMatch(String A, String B) {
		if (A.contains(B)) {
			return 1;
		}
		int n1 = A.length();
		int n2 = B.length();
		int i = 0, j = 0;
		int firstLen = n1;
		for (; firstLen > 0; firstLen--) {
			int j1 = firstLen - 1;
			int i1 = n1 - 1;
			boolean tag = true;
			while (j1 >= 0) {
				if (j1 >= n2 || A.charAt(i1--) != B.charAt(j1--)) {
					tag = false;
					break;
				}

			}
			if (tag) {
				break;
			}
		}
		// System.out.println(firstLen);
		if (firstLen == 0) {
			return -1;
		}
		j = firstLen;
		int count = 1;
		while (j < n2) {
			if (i == 0) {
				count++;
			}
			if (A.charAt(i) != B.charAt(j)) {
				return -1;
			}
			i++;
			j++;
			if (i == n1) {
				i = 0;
			}
		}
		return count;
	}

	public int repeatedStringMatc3(String A, String B) {
		int n1 = A.length();
		int n2 = B.length();
		int repeatTimes = (n2 / n1);
		if (n2 % n1 != 0) {
			repeatTimes++;
		}
		StringBuilder SA = new StringBuilder();
		for (int i = 0; i < repeatTimes; i++) {
			SA.append(A);
		}
		if (SA.indexOf(B) != -1) {
			return repeatTimes;
		}

		repeatTimes++;
		SA.append(A);
		if (SA.indexOf(B) != -1) {
			return repeatTimes;
		}

		repeatTimes++;
		SA.append(A);
		if (SA.indexOf(B) != -1) {
			return repeatTimes;
		}
		return -1;
	}

	public int repeatedStringMatch2(String A, String B) {
		int n1 = A.length();
		int n2 = B.length();
		int startLen = -1;
		for (int i = 0; i < n1; i++) {// 起始位置
			if (B.startsWith(A.substring(i))) {
				startLen = n1 - i;
			}
		}
		if (startLen == -1) {
			return -1;
		}
		int count1 = 1;
		n2 -= startLen;
		int repeatTimes = (n2 / n1);
		int BIndex = startLen;
		for (int i = 0; i < repeatTimes; i++) {
			for (int j = 0; j < n1; j++) {
				if (A.charAt(j) != B.charAt(BIndex++)) {
					return -1;
				}
			}
		}
		count1 += repeatTimes;
		int AIndex = 0;
		while (BIndex < n2) {
			if (A.charAt(AIndex++) != B.charAt(BIndex++)) {
				return -1;
			}
		}
		if (n2 % n1 != 0) {
			count1++;
		}
		return count1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String A = "abab", B = "aba";
		System.out.println(new RepeatedStringMatch().repeatedStringMatch(A, B));
	}

}
